1. Field of the Invention
The present invention is related to the field of data processing systems, and more particularly, the present invention relates to digital memories and other devices which require high speed comparison of data words.
2. Art Background
There are many instances in modem data processing systems wherein a central processing unit (CPU) or other device must determine whether or not two data words are identically equal. For example, a comparison operation between a first and a second data word may be required in the case of a cache memory system in which data words and/or memory tags must be compared, as well as in other digital systems such as encryption devices wherein passwords and the like must be compared for an identical match. One prior art system for the comparison of two data words is illustrated in FIG. 1. As shown in the Figure, a data word A is comprised of a plurality of bits A.sub.0, A.sub.1, A.sub.2, through A.sub.N. A second data word B is comprised of bits B.sub.0, B.sub.1, B.sub.2, through B.sub.N. A bit by bit comparison is accomplished through the use of a comparator circuit, shown conceptually in FIG. 1, to determine whether each of the corresponding bits in word A and word B are identical. Using the convention that if there is an identical match between the corresponding bits of word A and word B, a logical one results, a comparison between, for example, bit A.sub.2 (a logical zero) and bit B.sub.2 (a logical zero) results in a comparator value of a logical one. A comparison of bit A, (a logical one) with bit B, ( a logical zero) results in a comparator value of a logical zero (no match). The output from each of the compare operations is provided to a result circuit. The result circuit determines whether the comparison of each of the corresponding bits comprising word A and word B are equivalent. If word A and word B are identical, the result circuit generates a signal indicating that a match exists. If, however, as in the present example, one or more of the corresponding bits in word A and word B do not match, the result circuit generates a signal indicating that there is no match.
In some schemes, the prior art system illustrated in FIG. 1 is implemented using an architecture similar to that illustrated in FIGS. 2(a) and 2(b). As shown in FIG. 2(a), the four combinations possible for a comparison between, for example, bit A.sub.0 and bit B.sub.0 are shown in the Figure. The use of an exclusive NOR operation between the bit values of A.sub.0 and B.sub.0 provides a result C.sub.0. Each of the exclusive NOR operations between the corresponding bits comprising word A and word B are exclusive "NORed" together in a tree structure. As shown in FIG. 2(b), each of the exclusive NOR operations between the corresponding bits of word A and word B are, in ram, exclusive NORed together, until a final single output is obtained resulting in the generation of either a match or a no match signal.
A disadvantage of the tree structure illustrated in FIG. 2(b) is that the propagation of the signals through the exclusive NOR tree structure is delayed by each NOR operation. Performance is degraded as a result of the inherent delays associated with the tree structure. In addition, the delay which is incurred is a function of the width of the two words which are compared. Since modem computer systems increasingly utilize longer word lengths, the time required to compare two words becomes unacceptably long and negatively impacts overall system performance.
As will be described, the present invention provides a high performance compare circuit which incurs minimal delay and may be used in high performance computer systems. The present invention utilizes a dynamic compare method and apparatus which overcomes the historic limitations of prior art static comparison systems, such as those described above with reference to FIGS. 1 and 2.